在LeetCode商店中， 有许多在售的物品。

然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。

每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。

任意大礼包可无限次购买。

输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释: 
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。


class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        #你不可以购买超出待购清单的物品，即使更便宜。
        #dp的话维度有点大 6种物品 每个物品最多6种 算上礼包 100*6^6 不好coding实现啊
        #退而求其次 选择DFS+memo 记忆化搜索 学习官方题解的方法
        #在DFS+减枝的基础上  在加入记忆化存储部分搜索结果（其实可以看成一种减枝 减去重复的枝叶）
        
        #一个对象能不能作为字典的key，就取决于其有没有__hash__方法。所以所有python自带类型中，
        #除了list、dict、set和内部至少带有上述三种类型之一的tuple之外，其余的对象都能当key。
        #比如数值/字符串/完全不可变的元祖/函数(内建或自定义)/类(内建或自定义)/方法/包等等你能拿出手的，不过有的实际意义不高。
        #还有数值型要注意，因为两个不同的相等数字可以有相同的哈希值，比如1和1.0。
        def list2ID( needs )->int:
            ID = 0
            for n in needs:
                ID = ID*10 + n
            return ID
        
        def chooseSpecial(special, needs)->bool:
            for s, n in zip(special, needs):
                if s > n:
                    return False
            return True
        
        def withoutSpecial( needs )->int:
            total = 0
            for p, n in zip(price, needs):
                total += p*n
            return total
        
        def remanentNeeds(special, needs)->list:
            return [ n-s for n, s in zip(needs, special) ]

        
        memo = {}
        def DFS( needs ):
            ID = list2ID(needs)
            if ID in memo:
                return memo[ID]
            
            res = withoutSpecial( needs ) #不使用礼包 肯定是最贵的
            
            for sp in special:
                if chooseSpecial(sp, needs):
                    res = min( res, sp[-1]+DFS( remanentNeeds(sp, needs) ) )
            
            memo[ID] = res
            return res
        
        return DFS(needs)#DFS其实就是最暴力的搜索 DFS是人类思考时序问题的最基本最自然（也是最暴力）的思路
    
        #不使用记忆化搜索 结果：执行用时：88 ms 内存消耗：13.6 MB 超越68.28%
        #使用记忆化 结果：执行用时：84 ms 内存消耗：13.8 MB 超越77.99%
        

只使用DFS是最暴力的所以可能性遍历 ->优化一点+减枝->优化一点+记忆化
极限的记忆化应该就是所有子问题不重复处理 就是DP
DFS+memo 应该是DP退而求其次的程度

DFS+memo 就是重复的情况 在先前的DFS中搜索过了 再遇到相同的情况就不形成搜索子树了







329. 矩阵中的最长递增路径
给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        #DSF+memo
        #这个memo怎么说呢 跟怎么到这个位置是没有关系的 因为是递增的
        #同时会发现因为是递增的 所以还不需要记录是否被访问导致的路径循环
        if not matrix:
            return 0
        
        ROW = len(matrix)
        COL = len(matrix[0])
        
        def neighbor(r, c):
            for nr, nc in ( (r-1, c), (r+1, c), (r, c-1), (r, c+1) ):
                if 0<=nr<ROW and 0<=nc<COL:
                    yield nr, nc
        
        memo = [ [ 0 for _ in range(COL) ] for _ in range(ROW) ]
        #要记忆化的话 需要记录的是从该节点出发的最长递增路径是多少
        #而不是像往常DFS一样记录一个深度。加深一层就+1
		#记忆化是要记住子问题的答案 而减少重复生成相同子问题的子树
        def DFS(r, c)->int:
            
            if memo[r][c]!=0:
                return memo[r][c]
            
            depth = 1 #往下没路了就是1
            for nr, nc in neighbor(r, c):
                if matrix[nr][nc] < matrix[r][c]:
                    depth = max( depth, 1+DFS(nr, nc) )
            
            memo[r][c] = depth
            return depth
        
        res = 1
        for r in range(ROW):
            for c in range(COL):
                res = max( res, DFS(r, c) )
        
        return res